package binaryTree;

import utils.binaryTreeUtil;
import utils.binaryTreeUtil.TreeNode;

public class diameterOfBinaryTree {
    int max;
    public int diameterOfBinaryTree(TreeNode root) {
        //其实就是求左右节点最大深度之和
        //可能在同一侧，不一定是左右
        
        diameter(root);
        return max;
    }
    public int diameter(TreeNode root){
        if (root==null) {
            return 0;
        }
        int ldiameter = diameter(root.left);
        int rdiameter = diameter(root.right);
        max=Math.max(ldiameter+rdiameter+1,max);
        return Math.max(ldiameter, rdiameter)+1;
    }
    public static void main(String[] args) {
        

    }
}
